
import math
import secrets

# 椭圆曲线 y^2 = x^3 + Ax + B
#在这种情况下，secp256k1的方程式为：y^2=x^3+7
import time

A = 0
B = 7

#算法的基点X、Y
BASE_X = 55066263022277343669578718895168534326250603453777594175500187360389116729240
BASE_Y = 32670510020758816978083085130507043184471273380659243275938904335757337482424

#算法的基点
BASE_POINT = (BASE_X, BASE_Y)

# The proven prime
P = 115792089237316195423570985008687907853269984665640564039457584007908834671663
# The order of the base point on the curve (number of points the base point generates under repeated addition)
N = 115792089237316195423570985008687907852837564279074904382605163141518161494337


# 此处输出的为最大公约数，x,y。满足jx+ky=1.
def extended_euclidean_algorithm(j, k):

    if j == k:
        return (j, 1, 0)
    else:
        i = 0
        j_array = [j]
        k_array = [k]
        q_array = []
        r_array = []

        prev_r_is_zero = False

        while not (prev_r_is_zero):
            q_array.append(k_array[i] // j_array[i])
            r_array.append(k_array[i] % j_array[i])
            k_array.append(j_array[i])
            j_array.append(r_array[i])
            i += 1
            if r_array[i - 1] == 0:
                prev_r_is_zero = True

        i -= 1
        gcd = j_array[i]

        x_array = [1]
        y_array = [0]

        i -= 1
        total_steps = i

        while i >= 0:
            y_array.append(x_array[total_steps - i])
            x_array.append(y_array[total_steps - i] - q_array[i] * x_array[total_steps - i])
            i -= 1

        return (gcd, x_array[-1], y_array[-1])  # 此处输出的为最大公约数，x,y。满足jx+ky=1.


# 求的模逆的值
def mod_inverse(j, n):

    (gcd, x, y) = extended_euclidean_algorithm(j, n)

    if gcd == 1:
        return x % n
    else:
        return -1



# 椭圆曲线中点加运算
def elliptic_add(p, q):


    if p == 0 and q == 0:
        return 0
    elif p == 0:
        return q
    elif q == 0:
        return p
    else:
        # Swap p and q if px > qx.
        if p[0] > q[0]:
            temp = p
            p = q
            q = temp
        r = []

        slope = (q[1] - p[1]) * mod_inverse(q[0] - p[0], P) % P

        r.append((slope ** 2 - p[0] - q[0]) % P)
        r.append((slope * (p[0] - r[0]) - p[1]) % P)

        return (r[0], r[1])


# 将椭圆曲线上的一个点添加到自身
def elliptic_double(p):

    r = []

    slope = (3 * p[0] ** 2 + A) * mod_inverse(2 * p[1], P) % P

    r.append((slope ** 2 - 2 * p[0]) % P)
    r.append((slope * (p[0] - r[0]) - p[1]) % P)

    return (r[0], r[1])


# 在椭圆曲线上用一个给定的点p进行标量乘法
def elliptic_multiply(s, p):

    n = p
    r = 0  # 0 representing a point at infinity

    s_binary = bin(s)[2:]  # convert s to binary and remove the "0b" in the beginning  将s转换为二进制，并删除开头的“0b”
    s_length = len(s_binary)

    for i in reversed(range(s_length)):
        if s_binary[i] == '1':
            r = elliptic_add(r, n)
        n = elliptic_double(n)

    return r


import secrets


def generate_private_key():
    """Return a truly random 256-bit integer value (32 bytes in hexadecimal).

    Returns:
        A random 32 bit  hexadecimal value.
    """
    # 返回的为随机的256位整数值（16进制的32个字节）
    return int(secrets.token_hex(32), 16)


def generate_public_key(private_key):

    # 返回一个由公钥生成的私钥，其公钥是安全的，因为他的计算方法为通过将生成器的点 "乘以 "一个巨大的整数（私钥）在一个巨大的领域。产生的点 (将被压缩并作为公钥返回)将经过许多椭圆加法的处理 以至于不可能猜到乘数（也就是私钥）。
    return elliptic_multiply(private_key, BASE_POINT)


def compress_public_key(key):

    # 返回一个压缩的公钥：取公钥的x值并加上 y值的奇偶校验位开始。
    # 判断密钥y的奇偶性
    # Parity of y-value
    if key[1] % 2 == 0:
        parity = '02'
    else:
        parity = '03'

    return parity + hex(key[0])[2:]  # hex() 用于将十进制数字转换成十六进制；key[0]为密钥的x值，前两位为校验数字，后面取从第3位开始。
    # Python中的十六进制值包含一个 "0x "前缀。[2:]去掉了这个前缀


def generate_key_pair(print_flag=True):

    private_key = generate_private_key()
    public_key = generate_public_key(private_key)


    # 进行了十六进制转换。
    if (print_flag):
        # Note that hex values in Python contains a "0x" prefix. [2:] chops off this prefix.
        print("Private Key: " + str(private_key))
        print("Private Key (hex): " + str(hex(private_key))[2:])  # Python中的十六进制值包含一个 "0x "前缀。[2:]去掉了这个前缀
        print("Public Key: " + str(public_key[0]) + str(public_key[1]))

        print("Public Key (hex): " + "04" + hex(public_key[0])[2:] + hex(public_key[1])[2:])  # 比特币添加了一个“04”前缀，表示这是一个未压缩的公钥
        print("Public Key (hex and compressed): " + compress_public_key(public_key))

    return (private_key, generate_public_key(private_key))


from hashlib import sha256
def double_hash(message):

    hashed_message = sha256(message.encode('utf-8')).hexdigest()
    hashed_message = sha256(hashed_message.encode('utf-8')).hexdigest()
    return int(hashed_message,16)



def hammingWeight(input):

    result  = bin(input)[2:].count('1')
    return result

# Note that this function can be checked with other SHA-256 hashing tools online.
# For example, https://emn178.github.io/online-tools/sha256.html (make sure to double hash, then convert the hash into integers).

def hashCut(hashMessage):
    strhashMessage = str(hashMessage)
    cutHashMessage = strhashMessage[18:68]
    a = int(cutHashMessage)
    return a


def sign(private_key, message):  # 私钥对消息签名
    starttime = time.time()
    print("签名过程如下：")

    # A secure random number for the signature
    k = secrets.randbelow(N-1)  # 产生一个0到P的随机数，其中randbelow()为secrets包的内置函数      随机数k
    print("随机数k为：%i" % (k))

    random_point = elliptic_multiply(k, BASE_POINT)  # 随机数*基点                      random_point = KG   即为P
    print("P点的X坐标为：%i，P点的Y坐标为：%i" % (random_point[0],random_point[1]))

    # Only the x-value is needed, as the y can always be generated using the curve equation y^2 = x^3 + 7
    rx = random_point[0] % N  # 随机的点有x，y的坐标，但是只取x：random_point[0]，模为N
    print("x的横坐标取余为：%i" %(rx))

    hashed_message = double_hash(message)  # 消息为上个函数计算的双重哈希的消息             hashed_message即为消息的哈希值 e
    print("消息的哈希值为：%i" % (hashed_message))


    hamweight_hm =  hammingWeight(hashed_message)   #消息M的双重哈希之后的汉明重量         hamweight_hm即为消息哈希值的汉明重量 w
    print("消息哈希值的汉明重量为：%i" % (hamweight_hm))

    z = hashCut(hashed_message)

    k1 = secrets.randbelow(N-1)   # 产生一个0到P的随机数，其中randbelow()为secrets包的内置函数
    k2 = secrets.randbelow(N-1)
    k3 =  (k - (k1*rx + z*hamweight_hm*k2 )) % N

    #k = k1*rx + z*k2 + hashed_message*k3


    signature_proof = (rx*k1 - (hamweight_hm * z +rx) *private_key)  % N

    endtime = time.time()

    print('总共的时间为:', round(endtime - starttime, 2),'secs')
    return (rx, signature_proof,k2,k3)




def verify(public_key, message, signature):
    starttime = time.time()

    print("验证过程如下：")
    # (rx, s , k2 , k3 ) = signature  # 为签名的形式
    rx = signature[0]
    s  = signature[1]
    k2  = signature[2]
    k3  = signature[3]

    if rx>0 and rx <N and s>0 and s <N and k2>0 and k2 <N and k3>0 and k3 <N:
        hashed_message = double_hash(message)  # 双重签名得到的哈希消息
        print("消息的哈希值为：%i" % (hashed_message))

        hamweight_hm = hammingWeight(hashed_message)  # 消息M的双重哈希之后的汉明重量
        print("消息哈希值的汉明重量为：%i" % (hamweight_hm))

        z = hashCut(hashed_message)

        # Solve for the random point

        a = elliptic_multiply((s + z * hamweight_hm * k2 + k3) % N, BASE_POINT)
        b = elliptic_multiply((hamweight_hm * z + rx) % N, public_key)

        recovered_random_point = elliptic_add(a, b)
        endtime = time.time()

        print('总共的时间为:', round(endtime - starttime, 2), 'secs')
        return recovered_random_point[0] == rx  # 相等则表示验证通过
    else:
        return 0


(sample_private_key, sample_public_key) = generate_key_pair(False)
message = "验证签名是否通过呢"
print("我要签名的消息是：%s" % message)
signature = sign(sample_private_key, message)

if verify(sample_public_key, message, signature):
    print("签名通过")
else:
    print("签名失败")




